package com.husd.leetcode.math;

/**
 * 4、寻找两个有序数组的中位数
 * <p>
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author hushengdong
 * @date 2020/3/27
 */
public class FindMedianSortedArrays {

    /**
     * 作者：编程半岛
     * 链接：https://www.nowcoder.com/discuss/196951
     * 来源：牛客网
     * <p>
     * 理解一个有序数组中位数求解过程后，对于两个有序数组来说，
     * 我们只要找出第(m+n+1)/2大的数和第(m+n+2)/2大的数，然后求平均数即可。
     * 注意这里的第(m+n+1)/2大的数中m和n分别指两个数组的大小，
     * m+n如图1中的muns.length，第(m+n+1)/2大的数是指我们假设这两个数组组合成一个有序数组后找出第(m+n+1)/2大的数
     * （这里为什么没有像图1中进行减1？因为我们这里说的第几大的数下标是从1开始的；而图1中需要减1是因为使用的数组，下标是从0开始的）。
     * <p>
     * 接下来我们在这两个有序数组中找到第(m+n+1)/2大的数和第(m+n+2)/2大的数，
     * 抽象后可表述为在两个有序数组中找第k大的数。由于题目要求我们的时间复杂度为O(log(m+n))，
     * 我们很容易联想到二分查找。当查找时，我们还需要考虑一些特殊情况：
     * (1) 当某个数组查找的起始位置大于等于该数组长度时，说明这个数组中的所有数已经被淘汰，
     * 则只需要在另一个数组找查找即可。(2)如果k=1时，即需要查找第一个数，
     * 则找到两个数组起始位置中最小的那个即可。处理完特殊情况后，
     * 我们来分析一般情况。这里所说的二分是指对数组的大小进行二分还是指对k进行二分。
     * 以前我们对一维数组进行二分查找时，一般都是对数组大小进行二分，而这里需要对k进行二分。
     * 意思是，我们需要在两个数组查找第k/2大的数，由于这两个数组的长度不定，
     * 有可能存在有一个数组中没有第k/2大的数，如果没有则赋值为整型最大值。
     * 对于查找的具体过程，详见java代码。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int m = nums1.length, n = nums2.length;
        int l = (m + n + 1) / 2;
        int r = (m + n + 2) / 2;
        return (getKth(nums1, 0, nums2, 0, l) + getKth(nums1, 0, nums2, 0, r)) / 2.0;
    }

    // 在两个有序数组中二分查找第k大元素
    private int getKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
        // 特殊情况(1)，分析见正文部分
        if (start1 > nums1.length - 1) return nums2[start2 + k - 1];
        if (start2 > nums2.length - 1) return nums1[start1 + k - 1];
        // 特征情况(2)，分析见正文部分
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        // 分别在两个数组中查找第k/2个元素，若存在（即数组没有越界），标记为找到的值；若不存在，标记为整数最大值
        int nums1Mid = start1 + k / 2 - 1 < nums1.length ? nums1[start1 + k / 2 - 1] : Integer.MAX_VALUE;
        int nums2Mid = start2 + k / 2 - 1 < nums2.length ? nums2[start2 + k / 2 - 1] : Integer.MAX_VALUE;

        // 确定最终的第k/2个元素，然后递归查找
        if (nums1Mid < nums2Mid)
            return getKth(nums1, start1 + k / 2, nums2, start2, k - k / 2);
        else
            return getKth(nums1, start1, nums2, start2 + k / 2, k - k / 2);
    }
}
